package com.lds.offer.demo;

import java.util.Arrays;

/**
 * @description: Offer 57. 和为s的两个数字
 * @author: lds
 * @create: 2022-10-08 09:07
 **/
public class Offer_57_和为s的两个数字 {

    //https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

    /**
     * 数组是递增的，所以可以使用双向指针计算数字
     * 10 20 30 40 50  target = 80
     * 如上数组，使用arr【0】 + arr【arr.length-1】 与 target 比较
     * 如果相等，则输出arr【0】 和 arr【arr.length-1】
     * 如果大于target，则将arr【arr.length-1】向前移一位，即arr【arr.length-2】
     * 如果小于target，则将arr【0】向后移一位，即arr【1】
     * 当前后指针指向同一位时，代表没有找到，返回null
     */

    public static void main(String[] args) {
        int[] arr = new int[] {2,7,11,15};
        int[] search = search(arr, 9);
        System.out.println(Arrays.toString(search));
    }

    public static int[] search(int[] arr,int target){
        int begin = 0;
        int end = arr.length-1;
        for (;;) {
            if (begin == end) {
                return null;
            }
            if (arr[begin] + arr[end] == target) {
                return new int[]{arr[begin],arr[end]};
            }
            else if (arr[begin] + arr[end] < target) {
                begin++;
            }
            else if (arr[begin] + arr[end] > target) {
                end--;
            }
        }
    }
}
